#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

class Solution
{
private:
  void backtrack(vector<vector<string>> &res, vector<string> &track, string s, int start)
  {
    if (start == s.length())
    {
      res.push_back(track);
      return;
    }
    for (int i = start; i < s.length(); i++)
    {
      if (isPalind(s.substr(start, i - start + 1)))
      {
        track.push_back(s.substr(start, i - start + 1)); // 递归树第一层for循环 取 a ab aab
        backtrack(res, track, s, i + 1);                 // 进入第一层for循环a的递归子树：a->ab
        track.pop_back();                                // 针对第一层for循环a pop掉 准备进入第一层for循环 ab的递归子树
      }
    }
  }

  bool isPalind(string s)
  {
    int left = 0;
    int right = s.length() - 1;
    while (left < right)
    {
      if (s[left] != s[right])
      {
        return false;
      }
      left++;
      right--;
    }
    return true;
  }

public:
  vector<vector<string>> partition(string s)
  {
    // 用DFS, 回溯需要用在track，因为track是全局变量，每一个递归子树产生的结果在track push进res后，需要撤销选择
    vector<vector<string>> res;
    vector<string> track;
    if (0 == s.length())
      return res;
    backtrack(res, track, s, 0);
    return res;
  }
};

int main()
{

  Solution solution = Solution();
  string s = "aab";

  vector<vector<string>> res = solution.partition(s);

  for (auto strs : res)
  {
    for (auto ch : strs)
    {
      cout << ch << ',';
    }
    cout << ']' << endl;
  }
}